module Graph_utilities where

import qualified Data.Graph.Inductive    as G
import qualified Debug.Trace             as T
import qualified Data.Maybe              as MB

-- get_parent :: G.DynGraph gr => G.Node -> gr a b -> G.Node
-- get_parent n g =
--   case G.match n g of
--     (Nothing, _) -> error "flrr3"
--     (Just ([(_,p)],_,_,_), _) -> p
--     (_) -> error "gdf4"

g_unsafe_match :: G.DynGraph gr => String -> G.Node -> gr a b -> G.GDecomp gr a b
g_unsafe_match msg n g =
  case G.match n g of
    (Nothing, _) -> error msg
    (Just d, g') -> (d,g')

g_unsafe_lab :: G.DynGraph gr => String -> gr a b -> G.Node -> a
g_unsafe_lab msg g n =
  case G.lab g n of
    Nothing -> error msg
    Just a -> a

-- Begin DFG manipulation, scheduling, etc.

-- Here's what the dfg will look like:
-- Nodes
--   - Instructions
--     - Real instructions
--     - Fake instructions (live-in, live-out)
--   - Nets
--     - Label with register number for debugging, I guess
--     - Also label with fanout and number of instances in the queue
--     - We could think of the 'any live-in' as a kind of net, maybe
-- Edges
--   - Labeled with a 'port number'; the order that the value is read or
--     written by the instruction.  This is important for queue ordering.
--     Oh, also we need order constraints that aren't data.  Let's say
--     0-9 are register dependencies; anything higher is 'other'
--
-- We also need the queue instructions, though they shouldn't appear in the
-- DFG

-- The edges in the DFG are labeled with ports so we can tell what
-- order things should be read and written.  'Normal' register dependencies
-- will be labeled 0..9.  (I don't think any instruction reads or writes more
-- than 10 registers.)
dfg_reg_port_lim :: Integer
dfg_reg_port_lim = 10

-- c_count = consumer count?  Used in scheduling.
-- data DfgNInfo = DfgNet { net_name::String, net_q_count::Int, net_c_count::Int}
data DfgNInfo = DfgNet (Maybe String)
              | DfgDup
              | DfgPass
              | DfgSwap
              | DfgDrop
              | DfgLiveIns
              | DfgLiveOuts
              | DfgOp String
              | DfgData
data DfgEInfo = DfgPort Integer
              | DfgSeq
instance Show DfgNInfo where
    show (DfgNet Nothing)  = "anon net"
    show (DfgNet (Just n)) = "net("++n++")"
    show (DfgOp disas)     = "op!" ++ disas
    show DfgDup            = "DfgDup"
    show DfgPass           = "DfgPass"
    show DfgSwap           = "DfgSwap"
    show DfgDrop           = "DfgDrop"
    show DfgLiveIns        = "DfgLiveIns"
    show DfgLiveOuts       = "DfgLiveOuts"
    show DfgData           = "data!"
instance Show DfgEInfo where
    show (DfgPort i) = "port "++show i
    show DfgSeq      = "seq"
instance Eq DfgEInfo where
    DfgSeq       == DfgSeq       = True
    (DfgPort _)  == DfgSeq       = False
    DfgSeq       == (DfgPort _)  = False
    (DfgPort p1) == (DfgPort p2) = p1 == p2

type Dfg = G.Gr DfgNInfo DfgEInfo

-- make a prototype dfg with pass, dup, swap, drop
dfg_template :: Dfg
gdup_id  :: G.Node
gpass_id :: G.Node
gswap_id :: G.Node
gdrop_id :: G.Node
live_in_hub_id :: G.Node
live_out_hub_id :: G.Node
queue_front :: G.Node
queue_back :: G.Node
out_queue_front :: G.Node
out_queue_back :: G.Node
(dfg_template, gdup_id, gpass_id, gswap_id, gdrop_id,
 live_in_hub_id, live_out_hub_id, queue_front, queue_back, out_queue_front, out_queue_back) =
  (g1,d,p,s,r,li,lo,qf,qb,oqf,oqb)
  where
    e :: Dfg
    e = G.empty
    [d,p,s,r,li,lo,qf,qb,oqf,oqb] = G.newNodes 10 e
    ns = [(d,DfgDup),(p,DfgPass),(s,DfgSwap),(r,DfgDrop),
          (li,DfgLiveIns),(lo,DfgLiveOuts),
          (qf,DfgData),(qb,DfgData),(oqf,DfgData),(oqb,DfgData)]
    g1 = T.trace ("qf:"++show qf++"  qb:"++show qb++"  oqf:"++show oqf++"  oqb:"++show oqb)
        G.insEdge (oqf, oqb, DfgSeq) (G.insEdge (qf, qb, DfgSeq) (G.mkGraph ns []))

dfg_is_seq :: DfgEInfo -> Bool
dfg_is_seq DfgSeq = True
dfg_is_seq _ = False

dfg_is_net :: DfgNInfo -> Bool
dfg_is_net (DfgNet _) = True
dfg_is_net _ = False

dfg_is_live_ins :: DfgNInfo -> Bool
dfg_is_live_ins DfgLiveIns = True
dfg_is_live_ins _ = False

dfg_is_live_outs :: DfgNInfo -> Bool
dfg_is_live_outs DfgLiveOuts = True
dfg_is_live_outs _ = False

-- Some important invariants
dfg_formal_live_ins_count  :: Dfg -> Int
dfg_formal_live_outs_count :: Dfg -> Int
dfg_formal_live_ins_count  =
    dfg_formal_live_ins_out_count dfg_is_live_ins  live_in_hub_id
dfg_formal_live_outs_count =
    dfg_formal_live_ins_out_count dfg_is_live_outs live_out_hub_id

dfg_formal_live_ins_out_count :: G.Graph gr => (DfgNInfo -> Bool) -> G.Node -> gr DfgNInfo DfgEInfo -> Int
dfg_formal_live_ins_out_count correct_label node_id dfg =
    if correct_label l
       && length p == length s
       && all (dfg_is_net . MB.fromJust . (G.lab dfg) . snd) p
       && all (dfg_is_net . MB.fromJust . (G.lab dfg) . snd) s
    then
        length p
    else
        error "dfdssdfads"
    where
      (p,_,l,s) = G.context dfg node_id

dfg_next :: G.Node -> Dfg -> Maybe G.Node
dfg_prev :: G.Node -> Dfg -> Maybe G.Node
dfg_driver :: G.Node -> Dfg -> Maybe G.Node
(dfg_next, dfg_prev, dfg_driver) =
    (dfg_next_prev True dfg_is_seq,
     dfg_next_prev False dfg_is_seq,
     dfg_next_prev False (not . dfg_is_seq))
    where
      dfg_next_prev next_not_prev l_filter nid dfg =
          case filter (\(_,_,l) -> l_filter l)
                      ((if next_not_prev then G.out else G.inn) dfg nid) of
            [] -> Nothing
            [(n_from,n_to,_)] -> Just (if next_not_prev then n_to else n_from)
            _:_:_ -> error "one next/prev"
dfg_unsafe_next   :: G.Node -> Dfg -> G.Node
dfg_unsafe_prev   :: G.Node -> Dfg -> G.Node
dfg_unsafe_driver :: G.Node -> Dfg -> G.Node
dfg_unsafe_next   n g = MB.fromJust $ dfg_next   n g
dfg_unsafe_prev   n g = MB.fromJust $ dfg_prev   n g
dfg_unsafe_driver n g = MB.fromJust $ dfg_driver n g

-- Stitch nid1 into the next/prev list before nid2
dfg_insert_before :: G.Node -> G.Node -> Dfg -> Dfg
dfg_insert_before nid1 nid2 dfg = dfg_e2
    where
      prev = dfg_unsafe_prev nid2 dfg
      dfg_snip = G.delLEdge (prev, nid2, DfgSeq) dfg
      dfg_e1   = G.insEdge  (prev, nid1, DfgSeq) dfg_snip
      dfg_e2   = G.insEdge  (nid1, nid2, DfgSeq) dfg_e1


g_unsafe_match_net :: G.DynGraph gr => String -> G.Node -> gr DfgNInfo b ->
                      (G.Adj b, Maybe String, G.Adj b, gr DfgNInfo b)
g_unsafe_match_net msg n g =
  case g_unsafe_match msg n g of
    ((pes,_,DfgNet name,ses), g') -> (pes, name, ses, g')
    _ -> error (msg++"(NN)")


port_num_mby :: (DfgEInfo, a) -> Maybe (Integer, a)
port_num_mby (DfgPort i, nid) = Just (i, nid)
port_num_mby _ = Nothing
ports :: [(DfgEInfo, a)] -> [(Integer, a)]
ports edges = MB.catMaybes (map (port_num_mby) edges)
